#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int deepth = 0;
        int leftDeepth = 0;
        int rightDeepth = 0;
        int max = 0;
        if (!root){
            deepth = 0;
        }else{
            deepth = 1;
            leftDeepth = maxDepth(root->left);
            rightDeepth = maxDepth(root->right);
            if (leftDeepth > rightDeepth){
                max = leftDeepth;
            }else{
                max = rightDeepth;
            }
            deepth += max;
        }
        return deepth;
    }
};

TreeNode* createTree(int deepth, uint32_t max)
{
    if (deepth <= 0) return NULL;
    int value = rand()%max;
    TreeNode* root = new TreeNode(value);
    TreeNode* ref = root;
    ref->left = createTree(deepth-1, max);
    ref->right = createTree(deepth-1, max);
    return root;
}

void printTree(TreeNode* root)
{
    if (!root) return;
    printf("%d ", root->val);
    printTree(root->left);
    printTree(root->right);
}

int main()
{
    Solution su;
    TreeNode* tree;
    int deepth;
    srand(clock());
    tree = createTree(13, 20);
    printTree(tree);
    printf("\r\n");
    deepth = su.maxDepth(tree);
    printf("tree deepth is %d\r\n", deepth);
    return 0;
}
